ROAM Algorithm Version 2.0 -- work in progress

[ROAM Algorithm Homepage]

"Realtime Optimal Adaptation for Planetary Geometry and Texture: 4-8 Tile Hierarchies" [PDF 10.7MB dated 2006-01-14] by Lok M. Hwa, UC Davis, Mark A. Duchaineau, LLNL, and Kenneth I. Joy, UC Davis Abstract -- The realtime display of huge geometry and imagery databases involves view-dependent approximations, typically through the use of precomputed hierarchies that are selectively refined at runtime. A classic motivating problem is terrain visualization, in which planetary databases involving billions of elevation and color values are displayed on PC graphics hardware at high frame rates. This paper introduces a new diamond data structure for the basic selective-refinement processing, which is a streamlined method of representing the well-known hierarchies of right triangles that have enjoyed much success in realtime, view-dependent terrain display. Regular-grid tiles are proposed as the payload data per diamond for both geometry and texture. The use of 4-8 grid refinement and coarsening schemes allows level-of-detail transitions that are twice as gradual as traditional quadtree-based hierarchies, as well as very high quality low-pass filtering compared to subsampling-based hierarchies. An out-of-core storage organization is introduced based on Sierpinski indices per diamond, along with a tile preprocessing framework based on fine-to-coarse, same-level and coarse-to-fine gathering operations. To attain optimal frame-to-frame coherence and processing-order priorities, dual split and merge queues are developed similar to the Realtime Optimally Adapting Meshes (ROAM) Algorithm, as well as an adaptation of the ROAM frustum culling techniques. Example applications of lake-detection and procedural terrain generation demonstrate the flexibility of the tile processing framework.

ROAM at 40 million triangles per second On modern graphics hardware using AGP chunks, ROAM is shown here running with 1.56 million triangles at 25.6 frames per second. The geometry in this case is generated procedurally during flight using midpoint displacement with smooth interpolatory subdivision. [NOTE 2003-03-24: On my new RADEON 9700 the roamtest code clocks in at 56 million tris/sec].

ROAM Tutorial Code -- Diamonds, Split-Only and Fast Split-Merge Code is provided to introduce the diamond data structure and its use in split-only and split-merge ROAM implementations. The diamond point of view is used for the main "backbone" data structure for the upcoming ROAM 2 Algorithm. The code is developed in several small steps, up through a full split-merge optimizer with fast bucket-based queues. It compiles under both windows and linux.

This page outlines and journals the recent best theory, debates, experiments and overall progress in the development of an updated and extended version of the Realtime Optimally Adapting Meshes (ROAM) Algorithm, to be called ROAM 2.

ROAM Version 2 contains all the efficiencies of the original ROAM, but is updated to:

1) use diamonds instead of triangles as the backbone data structure [completed]

2) be fast for modern graphics hardware through AGP chunking [completed] and, in addition, progressive vertex arrays [theory complete, partial implementation]

3) deal with texture split-merge (replacing clipmapping) [theory complete, partial implementation]

4) allow paging and streaming of geometry and texture [fairly complete implementation, not ready for prime time]

5) work on arbitrary geometry (not just terrain) [complete]

6) shade via pixel lighting to get full dynamic illumination without per-vertex artifacts [theory and software-only implementation -- see LibGen/Surftools/Mesh]

7) generate procedural geometry on the fly using high quality midpoint displacement [complete but not fancy] and possibly coarse-to-fine river basin generation [partial theory]

8) provide runtime occlusion culling as a kind of per-patch frustum culling [implementation by Lucas Ackerman looking good, not quite ready for prime time]

9) reduce storage and bandwidth with wavelet compression of the texture and geometry [theory complete, components complete but not integrated into a full view-dependent optimizer]

This is work in progress, by myself and others working at LLNL or at UC Davis. I gave author Trent Polack an early heads-up on the basic diamond data structure based on his interest in using it for a recent book, Focus On 3D Terrain Programming. The book contains tutorial material on the basic ROAM 2 backbone data structure, the diamond, along with its use in a split-merge ROAM implementation. Certainly I should acknowledge the great ideas from Lucas Ackerman, Peter Lindstrom, Valerio Pascucci, Ken Joy, David Sigeti, Alex Pomeranz, Ben Gregorski and many others that have permeated into this effort. I take full responsibility for any inaccuracies, ommisions or other discrepancies on these pages. This web site (and related code) is maintained as a personal hobby in my spare time and should not be considered to be affiliated with my employer.

-- Mark Duchaineau, duchaine@cognigraph.com

Updated 2011-10-10 -- made more generic link to Trent Polack's book

Updated 2003-02-20

Updated 2008-01-22 -- corrected spelling of "Polack" and updated link to his book

Updated 2008-08-01 -- added abstract and link to 2005 Hwa/Duchaineau/Joy paper